package 第一个只出现一次的字符;

import java.util.*;

//题目描述
//在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,
// 并返回它的位置, 如果没有则返回 -1（需要区分大小写）.（从0开始计数）
public class Solution
{
    public int FirstNotRepeatingChar(String str)
    {
        //使用哈希表存储，key是字符，value是出现的次数，扫描第一遍形成这个表
        //第二遍找到第一个value是1的字符
        //java里的hashmap不维护顺序,所以使用LinkedHashMap
        //判断输入
        if(str.length()==0)
            return -1;
        LinkedHashMap<Character, Integer> linkedHashMap = new LinkedHashMap<>();

        char[] chars = str.toCharArray();
        for (int i = 0; i < str.length(); i++)
        {
            int count=1;
            if (linkedHashMap.containsKey(chars[i]))
            {
                count= (int) linkedHashMap.get(chars[i]);
                count++;
                linkedHashMap.replace(chars[i],count);
            }
            else
            {
                linkedHashMap.put(chars[i],count);
            }

        }
        char res = (char)0;
        boolean flag=false;
        //第二遍找到第一个value是1的字符
        for (Iterator<Map.Entry<Character, Integer>> iterator=linkedHashMap.entrySet().iterator();iterator.hasNext();)
        {
            Map.Entry<Character, Integer> entry = iterator.next();
            if (entry.getValue()==1)
            {
                res=entry.getKey();
                flag=true;
                break;
            }
        }
        if (flag)
            return str.indexOf(res);
        else
            return -1;
    }

    //char字符可以转为256范围内的数字，定义一个大小为256的数组，对字符串依次遍历，字符转为数组的索引
    // 对应索引的数字加一，、
    // 同样的思想，不可以用位来做，更加缩小所占存储空间，位只能是0或1，只能表示存在不存在，不能表示出现的次数
    public int FirstNotRepeatingChar1(String str) {
        if(str==null || str.length() == 0)return -1;
        int[] count = new int[256];
        //用一个类似hash的东西来存储字符出现的次数，很方便
        for(int i=0; i < str.length();i++)
            count[str.charAt(i)]++;
        //其实这个第二步应该也是ka我的地方，没有在第一时间想到只要在遍历一遍数组并访问hash记录就可以了
        for(int i=0; i < str.length();i++)
            if(count[str.charAt(i)]==1)
                return i;
        return -1;
    }

    public static void main(String[] args)
    {
        Solution solution = new Solution();
        System.out.println(solution.FirstNotRepeatingChar("google"));
    }
}
